package com.y.lintcode;

/**
 * @author Y2014188432
 * 丑数-----> 只含素因子 2 3 5 的数字
 * 1 也可以视为一个丑数
 * 输入:
 *      一个数字 n
 * 结果:
 *      位于 n 的丑数
 *
 * 分析：一个大的丑数必定为一个小的丑数乘以[2,3,5] 得到，在已经确定的丑数列中，前面的某个数乘以[2,3,5]即为
 * 后边一个的丑数，可以将首位丑数进行乘以[2,3,5],取最小值即为后一个的丑数，随后刻度进一
 */
public class Test3 {
    public static void main(String[] args) {
        int n = 7;
        System.out.println(test(n));
    }
    public static int test(int n){
        //简单情况下直接输出
        if (n <= 6){
            return n;
        }
        //正常处理
        int[] res = new int[n];
        res[0] = 1;
        int a = 0;
        int b = 0;
        int c = 0;
        for (int i = 1; i < n; i++) {
            res[i] = min(2*res[a],3*res[b],5*res[c]);
            System.out.println(a+"  "+b+"   "+c);
            if (res[i] == 2*res[a]){ a += 1; }
            if (res[i] == 3*res[b]){ b += 1; }
            if (res[i] == 5*res[c]){ c += 1; }
        }
        return  res[n - 1];
    }
    public static int min (int a,int b,int c){
        return Math.min(Math.min(a,b),c);
    }
}
